class Solution {//leetcode354——俄罗斯套娃信封问题
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[](vector<int>&lhs,vector<int>& rhs)->bool{
            return lhs[0]==rhs[0]?lhs[1]>rhs[1]:lhs[0]<rhs[0];
        });
        int n=envelopes.size();
        vector<int> ret;
        ret.push_back(envelopes[0][1]);
        for(int i=1;i<n;i++){
            if(envelopes[i][1]>ret.back()){
                ret.push_back(envelopes[i][1]);
            }
            else
            {
                int left=0,right=ret.size()-1;
                while(left<right){
                    int mid=(right-left)/2+left;
                    if(ret[mid]<envelopes[i][1]) left=mid+1;
                    else right=mid;
                }
                ret[right]=envelopes[i][1];
            }
        }
        return ret.size();
    }
};